1. Field of the Invention
This invention relates to computer databases. Specifically, this invention relates to methods of indexing database records which contain information describing the position, size and shape of objects in two and three-dimensional space.
2. Description of the Related Technology
The purpose of a data structure is to organize large volumes of information, allowing the computer to selectively process the data structure's content. The motivation for this is simple: you always have more data than your time requirements, processor speed, main memory and disk access time allow you to process all at once. Depending on the nature of the data and application, data organizing strategies may include partitioning the content into subsets with similar properties or sequencing the data to support indexing and hashing for fast random access. Databases and database management systems extend these concepts to provide persistent storage and transaction controlled editing of the structured data.
Spatial data such as that describing a two-dimensional map is no different in its need for efficient organization. Map data is particularly demanding in this regard. A comprehensive street map for a moderate sized community may consist of tens to hundreds of thousands of individual street segments. Wide area maps of LA or New York may contain millions of segments. The content of each map data object can also be some what bulky. For example, a record for an individual street segment may include the coordinates of its end points, a usage classification, the street name, street address ranges, left and right side incorporated city name and postal codes.
However, spatial data at its core poses a particularly vexing organizational problem because it tries to organize objects within two-dimensional space. Spatial coordinates consist of two (or more) values which are independent, but equally important for most spatial queries. Established data structures and database methods are designed to efficiently handle a single value, and not representations of multi-dimensional space.
This difficulty can be illustrated by considering the problem of creating an application which presents a small window of map data (for instance, the square mile surrounding a house) from a database of a few hundred thousand spatial objects (a map of the city surrounding the house). The motivation for doing this is really two fold: first, the typical resolution of a computer monitor is limited, allowing only a certain amount information to be expressed. Secondly, even if all the data fit within the monitor, the data processing time to calculate this much information (fetching, transforming, clipping, drawing) would be far too long for the average personal computer.
To solve this problem, it is advantageous to find all of the street segments which appear in the “window” that will be generated on the monitor, and avoid as many as possible which do not. Thus, all objects which are within a particular range of x-coordinate (or longitude) values and y-coordinate (or latitude) values will be gathered. This problem is generally known as rectangular window retrieval, and is one of the more fundamental types of spatial queries. This method will be used in the following sections as a method for gauging the effectiveness of each of the following organizational methods.
The most heavily researched and commonly used spatial data structures (data structures used to organize geographic and geometric data) rely on the concept of tile-based hierarchical trees. A tile in this context is a rectangular (or other regularly or irregularly shaped) partitioning of coordinate space, wherein each partition has a distinct line separating one tile from another so that no single point in the coordinate system lies within more than one tile. A hierarchical tree is one structure for dividing coordinate space by recursively decomposing the space into smaller and smaller tiles, starting at a root that represents the entire coordinate space. In this system, a “hard edge” between tiles means that every point in the space resides exactly one tile at each level of the hierarchy. No point can coexist in more than one tile.
One example of a well-known hierarchical tree is the quad-tree data structure. In one example, the quad-tree could represent the surface of the Earth. At the root of the quad-tree is a node representing the entire surface of the Earth. The root, in turn, will have four children representing each quadrant of Latitude and Longitude space: east of Greenwich and north of the Equator, east of Greenwich and south of the Equator, west of Greenwich and north of the Equator and finally, west of Greenwich and south of the equator. Points on Greenwich and the Equator are arbitrarily defined to be in one quadrant or the other. Each of these children are further subdivided into more quadrants, and the children of those children, and so on, down to the degree of partitioning which is required to support the volume and density of data which is to be stored in the quad-tree.
The principle problem with quad-tree structures is that they are unbalanced. Because each node in the tree has a limited data storage capacity, when that limit is exceeded, the node must be split into four children, and the data content pushed into lower recesses of the tree. As a result, the depth of a quad-tree is shallow where the data density is low, and deep where the data density is high. For example, a quad-tree used to find population centers on the surface of the Earth will be very shallow (e.g., have few nodes) in mid-ocean and polar regions, and very deep (e.g., have many nodes) in regions such as the east and south of the United States.
Since quad-trees are inherently unbalanced, the rectangular window retrieval behavior of a quad-tree is difficult to predict. It is difficult for software to predict how many nodes deep it may have to go to find the necessary data. In a large spatial database, each step down the quad-tree hierarchy into another node normally requires a time-consuming disk seek. In addition, more than one branch of the tree will likely have to be followed to find all the necessary data. Second, when the content of the data structure is dynamic, efficient space management is problematic since each node has both a fixed amount of space and a fixed regional coverage. In real world data schemes, these two rarely correspond. There are several variations on the quad-tree which attempt to minimize these problems. However, inefficiencies still persist.
So far, data structures containing points have only been discussed where each spatial object comprises a single set of coordinates. Lines, curves, circles, and polygons present a further complexity because they have dimensions. Therefore, these objects no longer fit neatly into tile based data structures, unless the tiling scheme is extremely contrived. There will always be some fraction of the objects which cross the hard edged tile boundaries from one coordinate region to another. Note that this fact is true regardless of the simplicity of an object's description. For example, a line segment described by its two end points, or a circle described by its center point and radius.
A simple, and commonly used way around this problem is to divide objects which cross the tile boundaries into multiple objects. Thus, a line segment which has its end points in two adjacent tiles will be split into two line segments; a line segment which starts in one tile, and passes through fifty tiles on its way to its other end will be broken into fifty-two line segments: one for each tile it touches.
This approach can be an effective strategy for certain applications which are read-only. However, it is a poor strategy for data structures with dynamic content. Adding new data objects is relatively simple, but deleting and modifying data are more difficult. Problems arise because the original objects are not guaranteed to be intact. If a line segment needs to be moved or removed, it must somehow be reconstituted so that the database behaves as expected. This requires additional database bookkeeping, more complicated algorithms and the accompanying degradation in design simplicity and performance.
Another general problem related to organizing multidimensional objects is that many of these objects are difficult to mathematically describe once broken up. For example, there are numerous ways in which a circle can overlap four adjacent rectangular tiles. Depending on placement, the same sized circle can become two, three or four odd shaped pieces. As with a heavily fragmented line segment, the original “natural” character of the object is effectively lost.
An alternate strategy is to use indirection, where objects which cross tile boundaries are multiply referenced. However, each reference requires an extra step to recover the object, and the same object may be retrieved more than once by the same query, requiring additional complexity to resolve. When the number of objects in the database becomes large, this extra level of indirection becomes too expensive to create a viable system.
Another strategy used with quad-trees is to push objects which cross tile boundaries into higher and higher levels of the tree until they finally fit. The difficulty with this strategy is that when the number of map objects contained in the higher nodes increases, database operations will have to examine every object at the higher nodes before they can direct the search to the smaller nodes which are more likely to contain useful information. This results in a tremendous lag time for finding data.
Query Optimization in a Conventional DBMS
As discussed above, data which describes the position, size and shape of objects in space is generally called spatial data. A collection of spatial data is called a Spatial Database. Examples of different types of Spatial Databases include maps (street-maps, topographic maps, land-use maps, etc.), two-dimensional and three-dimensional architectural drawings and integrated circuit designs.
Conventional Database Management Systems (DBMS) use indexing methods to optimize the retrieval of records which have specific data values in a given field. For each record in the database, the values of the field of interest are stored as keys in a tree or similar indexing data structure along with pointers back to the records which contain the corresponding values.
DATABASE TABLE 1 shows an example of a simple database table which contains information about former employees of a fictional corporation. Each row in the table corresponds to a single record. Each record contains information about a single former employee. The columns in the table correspond to fields in each record which store various facts about each former employee, including their name and starting and ending dates of employment.
DATABASE TABLE 1The FormerEmployee database table.NameStartDateEndDateOther . . . P. S. BuckJun. 15, 1992Aug. 2, 1995Willy CatherJan. 27, 1993Jun. 30, 1993Em DickinsonSep. 12, 1992Nov. 15, 1992Bill FauknerJul. 17, 1994Feb. 12, 1995Ernie HemmingwayJun. 30, 1991May 14 ,1993H. JamesOct. 16, 1991Dec. 4, 1992Jim JoyceNov. 23, 1992May 8, 1993E. A. PoeJan. 14, 1993Apr. 24, 1995
EXAMPLE QUERY 1 shows a SQL query which finds the names of all former employees who started working during 1993. If the number of records in the former employee database were large, and the query needs to be performed on a regular or timely basis, then it might be useful to create an index on the StartDate field to make this query perform more efficiently. Use of a sequential indexing data structure such as a B-tree effectively reorders the database table by the field being indexed, as is shown in DATABASE TABLE 2. The important property of such sequential indexing methods is that they allow very efficient search both for records which contain a specific value in the indexed field and for records which have a range of values in the indexed field.
EXAMPLE QUERY 1SQL to find all former employees hiredduring 1993.select NamefromFormerEmployeewhereStartDate ≧ Jan. 1, 1993andStartDate ≦ Dec. 31 ,1993
DATABASE TABLE 2The FormerEmployee table indexed by StartDate.NameStartDateEndDateOther . . . Ernie HemmingwayJun. 30, 1991May 14, 1993H. JamesOct. 16, 1991Dec. 4, 1992P. S. BuckJun. 15, 1992Aug. 2, 1995Em DickinsonSep. 12, 1992Nov. 15, 1992Jim JoyceOct. 23, 1992May 8, 1993E. A. PoeJan. 14, 1993Apr. 24, 1995Willy CatherJan. 27, 1993Jun. 30, 1993Bill FauknerJul. 17, 1994Feb 12, 1995
For analytical purposes, the efficiencies of computer algorithms and their supporting data structures are expressed in terms of Order functions which describe the approximate behavior of the algorithm as a function of the total number of objects involved. The notational short hand which is used to express Order is O0. For data processing algorithms, the Order function is based on the number of objects being processed.
For example, the best sorting algorithms are typically performed at a O(N×log(N)) cost, where N is the number of records being sorted. For data structures used to manage objects (for instance, an index in a database), the Order function is based on the number of objects being managed. For example, the best database indexing methods typically have a O(log(N)) search cost, where N is the number of records being stored in the database. Certain algorithms also have distinct, usually rare worst case costs which may be indicated by a different Order function. Constant functions which are independent of the total number of objects are indicated by the function O(K).
B-trees and similar Indexed Sequential Access Methods (or ISAMs) generally provide random access to any given key value in terms of a O(log(N)) cost, where N is the number of records in the table, and provide sequential access to subsequent records in a O(K) average cost, where K is a small constant representing the penalty of reading records through the index, (various strategies may be employed to minimize K, including index clustering and caching). The total cost of performing EXAMPLE QUERY 1 is therefore O(log(N)+(M×K)), where M is the number of records which satisfy the query. If N is large and M is small relative to N, then the cost of using the index to perform the query will be substantially smaller than the O(N) cost of scanning the entire table. DATA TABLE 1 illustrates this fact by showing the computed values of some Order functions for various values of N and M. This example, though quite simple, is representative of the widely used and generally accepted database management practice of optimizing queries using indexes.
FORMULA 1Cost of retrieving consecutive records from adatabase table via an index.O(log(N) + (M × K))whereN = number ofrecords in the table,M = number ofconsecutive recordswhich satisfythe query,K = constantextra cost of readingrecordsthrough the index.
EXAMPLE QUERY 2 shows a SQL query which finds the names of all former employees who worked during 1993. Unlike EXAMPLE QUERY 1, it is not possible to build an index using traditional methods alone which significantly improves EXAMPLE QUERY 2 for arbitrary condition boundaries, in this case, an arbitrary span of time. From a database theory point of view, the difficulty with this query is due to the interaction of the following two facts: because the two conditions are on separate field values, all records which satisfy one of the two conditions need to be inspected to see if they also satisfy the other; because each condition is an inequality, the set of records which must be inspected therefore includes all records which come either before or after one of the test values (depending on which field value is inspected first).
EXAMPLE QUERY 2SQL to find all former employees who workedduring 1993.select Namefrom FormerEmployeewhere EndDate ≧ Jan. 1, 1993and StartDate ≦ Dec. 31, 1993
Consider the process of satisfying EXAMPLE QUERY 2 using the index represented by DATABASE TABLE 2. The cost of performing EXAMPLE QUERY 2 using an index based on either of the two fields would be O(K×N/2) average cost and O(K×N) worst-case cost. In other words, the query will have to look at half the table on average, and may need to inspect the whole table in order to find all of the records which satisfy the first of the two conditions. Since the cost of scanning the entire table without the index is O(N), the value of using the index is effectively lost (refer to TABLE 3). Indeed, when this type of circumstance is detected, query optimizers (preprocessing functions which determine the actual sequence of steps which will be performed to satisfy a query) typically abandon the use of an index in favor of scanning the whole table.
FORMULA 2Cost of retrieving all records which overlap an intervalusing a conventional database index on the start or end value.O(K × N/2) average,O(K × N) worst case.
DATA TABLE 1Comparison of Order function results for various valuesof N and M. A K value of 1.5 is used for the purpose ofthis example.N, O(N)MO(log(N))O(log(N) + (M × K))O(K × N / 2)100521075100102177510050277751000531175010001031875010005037875010000541275001000010419750010000504797500
From a more abstract point-of-view, the difficulty with this example is that there is actually more information which the conventional database representation does not take into account. StartDate and EndDate are in fact two different facets of a single data item which is the contained span of time. Put in spatial terms, the StartDate and EndDate fields define two positions on a Time-Line, with size defined by the difference between those positions. For even simple one-dimensional data, conventional database management is unable to optimize queries based on both position and size.
Introduction to two-dimensional Spatial Data
Spatial databases have a particularly demanding need for efficient database management due to the huge number of objects involved. A comprehensive street map for a moderate sized community may consist of tens to hundreds of thousands of individual street blocks; wide area maps of Los Angeles, Calif. or New York, N.Y. may contain more than a million street blocks. Similarly, the designs for modem integrated circuits also contain millions of components.
FIG. 1 illustrates a coordinate plane with X- and Y-axes. For the purpose of the following example, the size of the plane is chosen to be 200×200 coordinate units, with the minimum and maximum coordinates values of −100 and 100 respectively for both X and Y. However, it should be noted that the principles discussed for the following example can be applied to any bounded two-dimensional coordinate system of any size, including, but not limited to planer, cylindrical surface and spherical surface coordinate systems. The latitude/longitude coordinate system for the earth's surface, with minimum and maximum latitude values of −90 degrees and +90 degrees, and minimum and maximum longitude values of −180 degrees and +180 degrees, is an example of one such spherical coordinate system.
FIG. 2 illustrates a distribution of points on the FIG. 1 plane. Ad discussed above, points are the simplest type of spatial data object. Their spatial description consists of coordinate position information only. An example of non-spatial description commonly associated with point objects might include the name and type of a business at that location, e.g., “Leon's BBQ”, or “restaurant”.
FIG. 3 illustrates a distribution of linear and polygonal spatial data objects representing a map (note that the text strings “Hwy 1” and “Hwy 2” are not themselves spatial data objects, but rather labels placed in close proximity to their corresponding objects). The spatial descriptions of linear and polygonal data objects are more complex because they include size and shape information in addition to solely their position in the coordinate system. An example of non-spatial description commonly associated with linear map objects might include the names and address ranges of the streets which the lines represent, e.g., “100–199 Main Street”. An example non-spatial description commonly associated with polygonal map objects are the name and type of the polygon object, e.g., “Lake Michigan”, “a great lake”.
FIG. 4 illustrates the Minimum Bounding Rectangles (MBRs) of various of linear and polygonal spatial data objects. The Minimum Bounding Rectangle of a spatial data object is the smallest rectangle orthogonal to the coordinate axis which completely contains the object. Minimum Bounding Rectangles are typically very easy to compute by simple inspection for the minimum and maximum coordinate values appearing in the spatial description. In spatial data storage and retrieval methods, Minimum Bounding Rectangles are often used represent the approximate position and size of objects because the simple content (two pairs of coordinates) lends itself to very efficient processing.
Storing two-dimensional Spatial Data in a Conventional Database Management System
DATABASE TABLE 3 shows how some of the points from FIG. 2 might be represented in a regular database table. The points in DATABASE TABLE 3 correspond to the subset of the points shown in FIG. 2 indicated by the * markers. EXAMPLE QUERY 3 shows a SQL query which fetches all points within a rectangular window. A rectangular window query is among the simplest of the commonly used geometric query types. Inspection reveals that “Emily's Bookstore” is the only record from DATABASE TABLE 3 which will be selected by this query. FIG. 5 shows the rectangular window corresponding to EXAMPLE QUERY 3 superimposed on the points shown in FIG. 2.
DATABASE TABLE 3A conventional database table containing somebusiness locations.XYNameType−4225Leon's BBQRestaurant9−34Super SaverGrocery Store1721Emily's BooksBook Store68−19Super SleeperMotel−847Bill's GarageGas Station
EXAMPLE QUERY 3SQL to find all businesses in a window.select Name, Typefrom BusinessLocationwhere X ≧ 10 and X ≦ 35and Y ≧ 15 and Y ≦ 40
The principle problem illustrated by this example is that the traditional query optimization method of building a simple index doesn't work well enough to be useful. Consider building an index based on the X field value. Use of this index to satisfy EXAMPLE QUERY 3 will result in an over-sampling of the database table illustrated by the two thick vertical bars shown in FIG. 6. When the query is performed, the records for all point objects which are between those two bars will need to be examined to find the much smaller subset which actually fits within the shaded window. The “Super Saver” record of DATABASE TABLE 3 is an example of a record which would be needlessly examined.
While the work required to start the query is logarithmic, the expected number of point objects which are over-sampled is a linear function of the number of point objects in the database, as is shown by FORMULA 3. This means that the performance of this query will tend to degrade linearly as the number of objects in the database increases. When data volumes become large, this linear behavior will becomes much worse than the preferred O(log(N)), effectively making this style of solution ineffective. The same problem occurs with an index based on Y. The root cause of this problem is the fact that two-dimensional spatial coordinates consist of two values (X and Y) which are independent, but which are also equally important for most spatial queries. Conventional database management techniques are poorly suited to handling two-dimensional data.
FORMULA 3Average cost of performing a two-dimensionalrectangular window query using conventionaldatabase indexing methods, assuming a mostlyeven distribution in X.O(log(N) + (K × N × CX / WX))whereN = number ofrecords in the table,K = constantextra cost of readingrecordsthrough the index.CX = width of thecoordinatespace,WX = width of therectangle.Description of Related two-dimensional Spatial Data Structures
The problems which conventional database management methods have with spatial data have led to the development of a variety of special purpose data storage and retrieval methods called Spatial Data Structures. The Design and Analysis of Spatial Data Structures by Hanan Samet includes a review of many of these methods. Many of the commonly used spatial data structures rely on the concept of tile based hierarchical trees.
FIG. 7 shows a rectangular recursive decomposition of space while FIG. 8 shows how the tiles formed by that decomposition can be organized to form a “tree” (a hierarchical data structure designed for searching). Data structures of this type are called Quad-Trees. FIG. 9 shows the points from FIG. 2 distributed into the “leaf-nodes” of this Quad-Tree.
FIG. 10 shows the subset of the Quad-Tree which is contacted by the Rectangular Window Retrieval of EXAMPLE QUERY 3. Note the contrast between the two bottom level nodes which must be inspected in the Quad-Tree, versus the long stripe which must be inspected using conventional database indexing as shown in FIG. 6. All of the inspected points from the two nodes in FIG. 10 are at least in the neighborhood of the rectangle, whereas some points inside the stripe in FIG. 6 are literally at the far edge (bottom) of the coordinate system. While the difference in number of inspected points is not great due to the simplicity of this example, the performance contrast is dramatic when the number of point objects is very large. The Quad-Tree is much better suited to storing position based data because it simultaneously indexes along both axis of the coordinate system.
In the most basic implementation of Quad-Trees, each tile in the hierarchy corresponds to a “record” containing information which pertains to that tile. If the tile is at the root or at a branch level, the corresponding record will contain the coordinates of, and pointers to, the records for each child tile. If the tile is at the leaf level, the corresponding record contains the subset of the spatial data objects (point, line or polygon objects and their attributes) which are geometrically contained within the tile's perimeter. The Quad-Tree database “records” are stored in a disk file in breadth first or depth first order, with the root at the head of the file. There are also variations which keep some spatial data objects at higher levels of the hierarchy, and which don't actually create records for leaves and branches which are either mostly or completely empty. For instance, leaves 133 and 144 in FIG. 9 are both empty.
An advantage of the Quad-Tree data structure is that it exhibits O(log(N)) cost when the spatial density of data is fairly uniform, therefore resulting in a well balanced tree. The balance is driven by the construction algorithms which control the amount of branching. The amount of branching (and therefore the maximum depth) in a Quad-Tree is driven by an interaction between the local density of spatial data objects and the maximum number of such objects which can be accommodated in a leaf level record. Specifically, when the data storage in a leaf record fills up, the leaf is split into four children with its spatial data objects redistributed accordingly by geometric containment. Each time this happens, the local height of the tree increases by one. As a result of this algorithmic behavior, however, very high local data densities can cause Quad-Tree performance to degrade toward O(N) cost due to exaggerated tree depth.
There are also a wide variety of non-hierarchical uses of hard edged tiles within a coordinate system. One such method uses space filling curves to sequence the tiles. FIG. 11 shows such a sequencing of a 4×4 tiling using the Peano-Hilbert curve. The resulting tiles are 50 units on a side. The tiles thus sequenced can be stored in records similar to the leaves in a Quad-Tree, where the data stored in each record corresponds to the subset contained within the tile's perimeter. The records can be simply indexed by a table which converts tile number to record location.
The tiles can also be used as a simple computational framework for assigning tile membership. DATABASE TABLE 4 shows the business location database table enhanced with corresponding tile number field from FIG. 11. The tile number is determined by computing the binary representations of the X and Y column and row numbers of the tile containing the point, and then applying the well known Peano-Hilbert bit-interleaving algorithm to compute the tile number in the sequence. Building an index on the tile number field allows the records to be efficiently searched with geometric queries, even though they are stored in a conventional database. For instance, it is possible to compute the fact that the rectangular window SQL query shown in EXAMPLE QUERY 3 can be satisfied by inspecting only those records which are marked with tile numbers 8 or 9.
DATABASE TABLE 4The BusinessLocations database table enhance with a Tile field.TileXYNameType8−4225Leon's BBQRestaurant149−34Super SaverGrocery Store91721Emily's BooksBook Store1368−19Super SleeperMotel4−847Bill's GarageGas Station
Analysis of the expected cost of this system shows the importance of tile granularity which this and all similar systems share. Extrapolating from the Order function for database queries given in FORMULA 1, the order function for this method is given by FORMULA 4. For a fixed sized window retrieval rectangle, the expected number of tiles is given by FORMULA 5, (the 1 is added within each parentheses to account for the possibility of the window retrieval crossing at least one tile boundary). For a given average size window retrieval, the value of A in FORMULA 4 is therefore an inverse geometric function of the granularity of the tiling which can be minimized by increasing the granularity of the tiling. The expected number of points per tile is given by FORMULA 6. For a given average data density, the value of B in FORMULA 4 is therefore roughly a quadratic function of the granularity of the tiling which can be minimized by decreasing the granularity of the tiling. For a given average retrieval window size and average data density, the expected value of FORMULA 4 can therefore be minimized by adjusting the granularity of the tiling to find the point where the competing trends of A and B yield the best minimum behavior of the system.
FORMULA 4Expected cost of window retrieval using tile numbersembedded in a database table.O(A × (log(N) + K × B))whereA = expectednumber of tilesneeded tosatisfy the query,B = expectednumber of objectsassigned toeach tile.
FORMULA 5Expected number of tiles per retrieval.A = round_up(WX / T X + 1)× round_up(WY / T Y + 1)whereWX = width ofthe rectangle,TX = width of atile,WY = height ofthe rectangle,TY = height of atile.
FORMULA 6Expected number points per tile.B = T X × TY × DwhereTX = width of atile,TY = height of atile,D = averagedensity of points.
While this technique still over-samples the database, the expected number of records which will be sampled is a function of the average number of records in a tile multiplied by the average number of tiles needed to satisfy the query. By adjusting the tile size, it is possible to control the behavior of this method so that it retains the O(log(N)) characteristics of the database indexing scheme, unlike a simple index based only on X or Y coordinate. Oracle Corporation's implementation of two-dimensional “HHCODES” is an example of this type of scheme.
The problem which all tile based schemes suffer is that higher dimension objects (segments, polylines, polygons) don't fit as neatly into the scheme as do points as FIGS. 12 and 13 illustrate. FIG. 12 shows how the linear and polygonal data objects from FIG. 3 naturally fall into the various nodes of the example Quad-Tree. Note how many objects reside at higher levels of the Quad-Tree. Specifically, any object which crosses one of the lower level tiles boundaries must be retained at the next higher level in the tree, because that tile is the smallest tile which completely covers the object. This is the only way that the Quad-Tree tile hierarchy has of accommodating the object which might cross a boundary as a single entity.
FIG. 13 shows the dramatic impact which the data that is moved up the hierarchical tree has on the example rectangular window retrieval. Since linear and polygonal data has size in addition to position, some substantial subset will always straddle the tile boundaries. As the number of objects in the database grows, the number of objects which reside in the upper nodes of the quad-tree will also grow, leading to a breakdown of the performance benefit of using the structure. This problem is shared by all hard tile-boundaried methods (Quad-Trees, K-D Trees, Grid-Cells and others).
There are three principle ways used to get around the problem of managing objects that straddle tile boundaries: 1) break up any objects which cross tile boundaries into multiple fragments, thereby forcing the data objects to fit, 2) duplicate the objects once for each extra tile that the object touches, and 3) indirectly referencing each object, once for each tile that it touches. Fragmentation in particular is most often used in read-only map data applications. While each of these methods has its respective strengths, a weakness shared by all of them is the great increase in implementation complexity, particularly when the content of the spatial database must be edited dynamically. Note also that these techniques need to be applied to each of the offending objects, which, as the object population in the middle and upper level nodes of FIG. 13 shows, is likely to be a substantial fraction of the database.
The R-Tree (or Range-Tree) is a data structure which has evolved specifically to accommodate the complexities of linear and polygonal data. Like Quad-Trees, R-Trees are a hierarchical search structure consisting of a root and multiple branch levels leading to leaves which contain the actual spatial data. Unlike Quad-Trees which are built from a top-down regular partitioning of the plane, R-Trees are built bottom-up to fit the irregularities of the spatial data objects. Leaf-level records are formed by collecting together data objects which have similar size and locality. For each record, a minimum bounding rectangle is computed which defines the minimum and maximum coordinate values for the set objects in the record. Leaf records which have similar size and locality are in turn collected into twig-level'records which consist of a list of the minimum bounding rectangles of and pointers to each of the child records, and an additional minimum bounding rectangle encompassing the entire collection. These twig records are in turn collected together to form the next level of branches, iterating until the tree converges to a single root record. Well balanced R-Trees exhibit O(log(N)) efficiency.
The difficulty with R-Trees is that, since there definition is dependent on how the data content “fits” together to build the tree, the algorithms for building and maintaining R-Trees tend to be complicated and highly sensitive to that data content. Static applications of R-Trees, where the data content does not change, are the easiest to implement. Dynamic applications, where the data is constantly being modified, are much more difficult. This is in part because the edit operations which modify the geometric descriptions of the spatial data, by implication have the potential to change the minimum bounding rectangle of the containing record, which in turn can effect the minimum bounding rectangle of the parent twig record, and so on up to the root. Any operation therefore has the potential to cause significant reorganization of the tree structure, which must be kept well balanced to maintain O(log(N)) efficiency.
In summary, a variety of special purpose data structures have evolved to meet the particular requirements of multi-dimensional spatial data storage. While these techniques effectively solve some of the problems associated with two-dimensional spatial data, they also share the same inherent weakness which one-dimensional methods have when dealing with data which represents a continuous range of values. In the one-dimensional case, the problem data object types are closed intervals of a single variable, for example, intervals of time. In the two-dimensional case, the problem data object types such as lines, circles and polygons are described by closed intervals of two variables.
Description of three-dimensional and Higher Dimension Spatial Data Structures
Spatial data which describe a three-dimensional surface has similar requirements for efficient organization. The added complexity is that three-dimensional spatial data consists of 3 independent variables (X, Y and Z) which have equal weight. three-dimensional geometric descriptions of lines, surfaces and volumes are also more complicated than two-dimensional lines and polygons, which make the data somewhat bulkier.
However, the basic database organizational problems in three-dimensional are fundamentally the same as those in two-dimensional space, and are therefore amenable to very similar solutions. There is a three-dimensional equivalent to Quad-Tree which uses a regular cubic partitioning of three-dimensional space. Oracle Corporation has also implemented a three-dimensional version of its “HHCODE” technology for storing point objects. There is also a three-dimensional equivalent to R-Trees which uses three-dimensional minimum bounding boxes to define the coordinate extent of leaves and branches. These techniques also share the same limitations as one-dimensional and two-dimensional techniques when handling data representing continuous three-dimensional intervals.
The same principles also apply to organizing higher dimension data. In particular, Oracle Corporation has extended its “HHCODE” technology to accommodate point objects of up to 11 dimensions.
As described above, there are several problems associated with efficiently organizing and indexing multi-dimensional spatial data within a database. For this reason, an improved method for staring spatial data would be advantageous. This advantage is provided by the system of the present invention.